# class Solution:
#     def findRotateSteps(self, ring: str, key: str) -> int:
#         count=0
#         curr=0
#         step=0
#         while count<len(key):
#             for i in range(len(ring)):
#                 if ring[(curr+i)%len(ring)]==key[count]:
#                     curr=curr+i
#                     step+=i+1
#                     count+=1
#                     break
#                 elif ring[(curr-i)%len(ring)]==key[count]:
#                     curr=curr-i
#                     step+=i+1
#                     count+=1
#                     break
#         return step 


# class Solution:
#     def findRotateSteps(self, ring: str, key: str) -> int:
#         result=[]
#         def find(count,step,curr):
#             nonlocal ring,key
#             if count==len(key):
#                 result.append(step)
#                 return 
#             flag=False
#             i=0
#             while not flag:
#                 if ring[(curr+i)%len(ring)]==key[count]:
#                     find(count+1,step+i+1,curr+i)
#                     flag=True
#                 if ring[(curr-i)%len(ring)]==key[count] and i!=0:
#                     find(count+1,step+i+1,curr-i)
#                     flag=True
#                 i+=1
#         find(0,0,0)
#         return min(result)  





import math

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        result=[10000]
        mapper={i:[] for i in set(ring)}
        for i in range(len(ring)):
            mapper[ring[i]].append(i)
        print(mapper)
        def find(count,step,curr):
            #print(count,step,curr)
            nonlocal ring,key
            if count==len(key):
                if step<result[0]:
                    result[0]=step
                    print(result)
                return 
            if count>1 and key[count-1]==key[count]:
                find(count+1,step+1,curr)
            else:
                for i in mapper[key[count]]:
                    find(count+1,step+int(min([math.fabs(curr-i)+1,len(ring)-math.fabs(curr-i)+1])),i)
        find(0,0,0)
        return result[0]
s=Solution()
print(s.findRotateSteps(
"caotmcaataijjxi",
"oatjiioicitatajtijciocjcaaxaaatmctxamacaamjjx"))